The present invention relates to a distributed computing system having a plurality of computers connected to a network for cooperatively executing a plurality of programs, and more particularly to the configuration and method for such a distributed computing system which utilizes priority to realize real-time characteristics.
For ensuring real-time characteristics in a conventional computer system consisting only of a single computer (including a multi-processor type computer), there has been utilized an approach of controlling the order of programs to be processed based on the priority of the programs. xe2x80x9cOperating Systemsxe2x80x94Design and Implementationxe2x80x9d by A. S. Tanenbaum, published by Prentice-Hall, Inc. pp. 82-84, (1987) describes an example of such processing order control using the priority of the programs.
Also, JP-A-2-113362, for example, describes a control scheme in which priority information is added to each message, when communicated between processing nodes in a distributed computing system, such that the messages are processed in the order of priority starting from the message with the highest priority level (this system is hereinafter called the xe2x80x9cprior art 1xe2x80x9d).
Another conventional scheme is also described in JP-A-5-35701. This scheme specifies a tolerable processing pending time when a processing request is issued in a distributed computing system having a plurality of processors, examines a scheduled processing pending time of each processor, and assigns the processing request to a processor whose scheduled processing pending time is shorter than the tolerable processing pending time. If no processors satisfy the tolerable processing pending time, the processing request is assigned to the processor with the shortest scheduled processing pending time. Processing requests assigned to the respective processors are processed beginning with basically the oldest one (this system is hereinafter called the xe2x80x9cprior art 2xe2x80x9d).
Further, as described, for example, in JP-A-5-35701, when processing requests are issued, a tolerable processing pending time as well as a priority level, similar to the prior art 1, are added to each request such that the processing requests, after assigned to processors, are processed by the respective assigned processors in the order of the priority level (this method is hereinafter called the xe2x80x9cprior art 3xe2x80x9d).
In a distributed computing system in which a plurality of computers are managed by respective operating systems associated therewith, the priority of programs is separately managed in each of the computers. Therefore, the priority of programs to be executed by the respective computers cannot be managed uniformly in the whole distributed computing system. Particularly in a distributed computing system having computers which differ in performance and load, the urgency represented by the priority of a computer may differ from the urgency represented by the priority of another computer. More specifically, in comparison of a high-performance computer with a low-performance computer, the former can complete processing faster than the latter even if they execute the same processing having a priority level set to zero. Similarly, between a heavily loaded computer and a lightly loaded computer, the meaning given by their respective priority levels will be different from each other.
Moreover, in a distributed computing system having a plurality of different kinds of computers, the priority scheme itself may be different from one computer to another. For example, a computer having a priority level range from 0 to 255 is not compatible with a computer having a priority level range from 0 to 127 with respect to the value set to the priority level. Similarly, the same priority level cannot be used in a computer which regards priority level 0 as the highest rank as well as in a computer which regards priority level 255 as the highest rank.
The prior art 1 simply transmits a message together with a priority level without considering the difference in performance, load, and type among individual computers in a distributed computing system. Therefore, if a message is sent to a low-performance computer or a heavily loaded computer, it is probable that the processing is not executed at a desired speed, possibly resulting in failing to ensure the real-time characteristics.
Further, in the prior art 1, when a plurality of computers are requested to execute programs, a reverse phenomenon may occur, i.e., a request with a lower priority level is completed faster than a request with a higher priority level. For example, assume that processing A with priority level 5 is requested to a computer A, while processing B with priority level 1 to a computer B (assume also that a higher priority is represented by a smaller priority level). In this event, the processing B should have been completed faster than the processing A, for conforming to the original intention. However, if the performance of the computer B is lower than that of the computer A, or if the computer B is more heavily loaded than the computer A, it is possible that the processing A with lower priority be completed faster than the processing B with higher priority.
Furthermore, since the prior art 1 does not consider a situation in which processing requests concentrate on a single computer, particularly, a situation in which processing requests with higher priority levels concentrate on a single computer, the computer which has received a large number of requests with higher priority levels presents difficulties in ensuring the real-time characteristics.
The prior art 2, in turn, may be used to ensure the real-time characteristics to a certain extent for individual processing requests, provided that the scheduled processing pending time can be correctly calculated for the respective processors. However, this system may fail to satisfy a time limit condition for a processing request with a short tolerable processing pending time which is newly issued after a certain number of processing requests have already been assigned to respective processors. For example, even in a situation where, if a processor was able to process a newly issued processing request prior to processing requests with a long tolerable processing pending time which have already been assigned to processors, the time limit condition would be satisfied for all of the processing requests, the system of the prior art 2, which assigns processing requests in order, occasionally fails to satisfy the time limit condition for the newly issued processing request. In other words, the prior art 2 is incapable of immediately processing a highly urgent processing request which is issued in a relatively heavily loaded situation. Thus, the prior art 2 has a problem that strict real-time characteristics cannot be ensured.
The prior art 3, on the other hand, is a system which involves: (1) selecting a processor which meets a tolerable processing pending time in assigning a processing request to a processor; and (2) executing processing requests in the order of the priority levels accompanied to the respective requests in each of the processors. According to the prior art 3, the disadvantage of the prior art 2 can be solved to some degree by setting a high priority level to a newly issued processing request with a short tolerable processing pending time. However, since this system preferentially processes a newly assigned processing request with a high priority level, it may fail to satisfy a processing pending tolerable time of an already assigned processing request with a low priority level which was determined that its tolerable processing pending time would be satisfied. For example, assume that, in a situation where a processing request A with a tolerable processing pending time set to one minute and with priority level 5 has been assigned to a processor A, determined that the tolerable processing pending time thereof would be satisfied, a processing, request B with a tolerable processing pending time set to 30 seconds and with priority level 1 is newly assigned to the processor A. In this event, the processing request B is processed prior to the processing request A. This preferential execution may result in failing to satisfy the tolerable processing pending time of the processing request A which has already been assigned to the same processor and for which the tolerable processing pending time should have been ensured to be satisfied.
Also, in the prior art 3, when different processing requests with the same tolerable processing pending time but with different priority levels are assigned to a plurality of processors, a reverse phenomenon similar to that of the prior art 1 can occur due to the difference in load amount and performance among the assigned processors, where processing requested with a lower priority level can be completed faster than processing requested with a higher priority level.
It is therefore an object of the present invention to solve the problems associated with the above-mentioned real-time characteristics and to realize more strict real-time characteristics in a distributed computing system.
It is another object of the present invention to provide a distributed computing system possibly including different computers in performance, load, and type, which is capable of realizing more strict real-time characteristics by uniformly managing local priority schemes adapted in the respective computers.
The present invention employs either of the following two concepts for uniformly managing the local priority schemes adapted in respective computers which belong to a distributed computing system:
(1) urgency of processing: a common relative value employed in the whole system for indicating how fast processing is to be completed; and
(2) time limit on processing: an absolute value indicating how fast processing is preferably completed.
Means for the uniform management of the local priority schemes in respective computers in a distributed computing system, in accordance with the present invention, will hereinafter be described separately for the case where the urgency of processing is utilized and for the case where the time limit on processing is utilized.
To achieve the above object, according to one aspect, the present invention is characterized by priority level determining means for determining a priority level suitable for executing a program in consideration of at least one of the performance and the load of each computer and an urgency level of processing executed by the program.
Specifically, the priority level determining means has the following five means as its components which operate in cooperation with each other to enable the management of a distributed computing system for achieving the above objects utilizing the urgency of processing:
(1) priority level conversion means for performing a conversion between an urgency level and a corresponding priority level of processing in accordance with the performance and the load of a computer;
(2) priority level changing means for changing the priority level of a program which executes the processing in accordance with a priority level indicated by the priority level conversion means;
(3) computer selection means for determining a computer suitable for executing the program in consideration of at least one of the performance and the load of each computer and the urgency level of the processing executed by the program;
(4) program selection means, operative when a plurality of programs performing the same operation exist and processing is requested to one of these programs, for determining a program having an optimal priority level from the plurality of programs performing the same operation, in consideration of at least one of the performance and the load of each computer and the urgency level of the processing; and
(5) processing forward means for forwarding newly requested processing to a program indicated by the program selection means.
To achieve the above object, according to another aspect of the present invention, the present invention is characterized by priority level determining means f or determining a priority level suitable for executing a program in consideration of at least one of the performance and the load of each computer and a time limit and processing amount of processing executed by the program.
Specifically, the priority level determination means has the following eight means as its components which operate in cooperation with each other to enable the management of a distributed computing system for achieving the above objects utilizing the time limit of processing. It should be noted however.that all of the following eight means need not be provided simultaneously:
(1) priority level conversion means for performing a conversion between a set limit and a processing amount of processing and a priority level in accordance with the performance and the load of a computer;
(2) priority level changing means for changing the priority level of a program which executes a program in accordance with a priority level indicated by the priority level conversion means;
(3) communication time prediction means for predicting a communication time with another computer;
(4) computer selection means for determining a computer suitable for executing a program in consideration of at least one of the performance and the load of each computer as well as a set of a time limit and a processing amount of processing executed by the program;
(5) program selection means, operative when a plurality of programs performing the same operation exist and processing is requested to one of these programs, for determining a program having an optimal priority level from the plurality of programs performing the same operation, in consideration of at least one of the performance and the load of each computer and a set of the time limit and the processing amount of the processing;
(6) processing forward means for forwarding newly requested processing to a program indicated by the program selection means;
(7) processing time prediction means for predicting a processing time required for the program to complete processing currently in execution, in accordance with the performance, load, processing amount of the computer; and
(8) time limit setting means, operative when a predicted processing time does not satisfy the time limit imposed to the processing, for newly setting a time limit from an elapsed time from the time the processing was requested until passing of the imposed time limit.
The operation carried out by the means for solving the above-mentioned problems will be described separately for the case where the urgency of processing is utilized and for the case where the time limit of processing is utilized.
The priority level determining means determines a priority level suitable for executing a program in consideration of at least one of the performance and the load of each computer and the urgency level of processing executed by the program. This enables the processing to be completed at substantially the same speed irrespective of the difference in performance of the respective computers, by giving a low priority level to the program when executed on a high-performance computer and by giving a high priority level when executed on a low-performance computer. Similarly, the processing can be executed at substantially the same speed also irrespective of the difference in load of the respective computers by giving a high priority level to a heavily loaded computer and by giving a low priority level to a lightly loaded computer. Since the priority level is determined in each computer based on the urgency of processing in consideration of the performance and the load of each computer, it is possible to avoid a reverse phenomenon where processing with a lower urgency level is completed earlier than processing with a higher urgency level. Stated another way, more strict real-time characteristics can be ensured as compared with the prior art techniques. The five means constituting the priority level determining means have the following functions, respectively.
The priority level conversion means has a priority level correspondence table which is utilized for the conversion between an urgency level and a corresponding priority level of processing. The contents of the priority level correspondence table are modified in accordance with variations in performance, load, and type of computers. The priority level changing means changes the priority level of a program in accordance with a priority level indicated by the priority level conversion means. The priority level conversion means in cooperation with the priority level changing means ensure that processing having the same urgency level is executed at substantially the same speed by any of the computers which may be different in performance and load.
The computer selection means refers to computer information area composed of a computer performance information table and a computer load information table, selects a computer, to which a program with a specified urgency level is assigned, so as to equally distribute the load to the computers in the system, and has the selected computer execute the program. The computer performance information table shows the performances of the respective computers, while the computer load information table shows loads on the respective computers for each urgency level. When a load on any computer varies, this varying amount is reflected to the computer load information table. This prevents a multitude of processing with a high urgency level from concentrating on a single computer, thus making it possible to ensure more strict real-time characteristics in the respective computers.
The program selection means employs a program location database which contains information on programs performing the same operation to select a program having an urgency level coincident with a specified. urgency level from a group of programs performing the same operation. A processing request is then sent to the selected program. The program location database stores priority levels or urgency levels of programs performing the same operation and the identifiers of computers on which these programs run. Thus, even if the above-mentioned priority level changing means is not employed, it is possible to prepare a plurality of programs with different urgency levels, request a program with the most suitable urgency level selected from these programs to execute processing, and have the requested program execute the processing at a desired speed.
When a program currently executing processing is requested to execute other processing, the processing forward means inquires of the program selection means the locations of other programs performing the same operation as the requested program, and forwards the processing request to a program which was specified as a result by the program selection means. Thus, the new processing requested to the currently executing program can be executed by another program capable of executing the processing at substantially the same speed (with the same urgency level) without waiting for the completion of the currently executed processing by the requested program, thus ensuring more strict real-time characteristics.
The priority level determining means determines a priority level suitable for the execution of a program in consideration of at least one of the performance and the load of each computer as well as a set of a time limit and a processing amount of processing executed by the program. In this way, a set of the time limit and the processing amount of the processing are converted to a local priority level defined in each computer in accordance with the performance and the load of the computer, and the processing is executed with the converted priority level. Thus, it is possible to execute newly requested processing with a shorter time limit prior to previously assigned processing with a longer time limit. Also, since the time limit of processing can be converted to a local priority level in a computer in accordance with the performance and the load of the computer, if an elapsed time is approaching to a time limit of processing already assigned to a computer, the time limit of the processing is made shorter and a corresponding priority level is again determined in accordance with the shortened time limit to the processing, whereby newly requested processing will not hinder the execution of previously assigned processing. Stated another way, more strict real-time characteristics can be ensured as compared with the prior art techniques. The eight means constituting the priority level determination means have the following functions, respectively.
The priority level conversion means has a priority level correspondence table, indicating the correspondence between a time limit per unit processing amount and a priority level, which is employed to perform a conversion between a set of a time limit and a processing amount of processing and a corresponding priority level. The contents of the priority level correspondence table are modified in accordance with variations in performance, load, and type of computers.
The priority level changing means changes the priority level of a program in accordance with a priority level indicated by the priority level conversion means. The priority level conversion means in cooperation with the priority level changing means enable processing to be executed with a local priority level of each computer corresponding to a time limit imposed to the processing. It is therefore possible to execute processing with a shorter time limit prior to other processing with a longer time limit, thus ensuring more strict real-time characteristics for each processing in the distributed computing system. If even processing with a long time limit is left unexecuted in order to preferentially execute other processing with a short time limit, the elapsed time approaches the time limit of the processing that is left unexecuted. In this event, the priority level of the processing is corrected to a larger value in accordance with the shortened available time to the processing, so that the processing can be executed with the corrected priority level.
The communication time prediction means has a communication time table for holding a communication time with each computer and informs a time required for a communication with a certain computer when so requested. In this way, the time limit of processing can be more strictly set if the communication time between computers is not negligeable.
The computer selection means refers to a computer information area composed of a computer performance information table and a computer load information table, selects a computer, such that the load or processing with a specified time limit per unit processing amount is equally distributed to computers, and has the selected computer execute a program. The computer performance information table shows the performances of the respective computers, while the computer load information table shows loads on the respective computers for each urgency level. When a load on any computer varies, this varying amount is reflected to the computer load information table. This prevents a multitude of processing with a short time limit from concentrating on a single computer, thus making it possible to more strictly ensure the real-time characteristics in the respective computer.
The program selection means employs a program location database which contains information on programs performing the same operation to select a program, having a time limit per unit processing amount coincident with specified one, from a group of programs performing the same operation. A processing request is then sent to the selected program. The program location database stores either priority levels or urgency levels of programs performing the same operation and the identifiers of computers on which these programs run. Thus, even if the above-mentioned priority level changing means is not employed, it is possible to prepare a plurality of programs with different time limits, request a program with the most suitable time limit selected from these programs to execute processing, and have the requested program execute the processing at a desired speed.
When a program currently executing processing is requested to execute other processing, the processing forward means inquires of the program selection means the locations of other programs performing the same operation as the requested program, and forwards the processing request to a program which was specified as a result by the program selection means. Thus, the new processing requested to the currently executing program can be executed by another program capable of executing the processing at substantially the same speed without waiting for the completion of the currently executed processing by the requested program, thus ensuring more strict real-time characteristics.
The processing time prediction means calculates a time required to complete a program from a remaining processing amount to be executed by the program and a time limit per unit processing amount of the program.
The time limit setting means determines a new time limit for processing from a time limit of the processing specified upon requesting the processing and an elapsed time from the execution of the processing has been started. The time limit setting means, in corporation with the processing time prediction means, determines whether the time limit of the processing is satisfied if a program is executed with a current priority level. If it is determined that the time limit is not satisfied, a shorter time limit may be set. By the use of the newly set time limit the priority level conversion means and the priority level changing means can give a higher priority level to the program, and forward the processing to another program performing the same operation which can satisfy the new time limit to have this program execute the processing. In this way, the processing can be managed to satisfy the originally given time limit.